{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "R1CS to QAP\n", "=============" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "%load_ext autoreload\n", "%autoreload 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Example" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "# ref: https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649\n", "\n", "from functools import partial\n", "from klefki.zkp.r1cs import R1CS, mul\n", "from klefki.zkp.qap import QAP\n", "from klefki.curves.bns.bn128 import BN128FP as F\n", "from klefki.algebra.rings import PolyRing\n", "import ast\n", "\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "# map int to field\n", "ciphers = [1,2,3,4,5,6,7,8,9]\n", "times = 5\n", "\n", "@R1CS.r1cs(F)\n", "def f(x, k, c):\n", " y = x + c + k\n", " return y ** 3\n", "\n", "@R1CS.r1cs(F, globals())\n", "def mimc(x, k):\n", " for i in range(times):\n", " c = ciphers[i]\n", " x = f(x, k, c)\n", " return x + k" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[['add', 'Sym::0', 'x', 'c'],\n", " ['add', 'y', 'Sym::0', 'k'],\n", " ['mul', 'Sym::1', 'y', 'y'],\n", " ['mul', '~out', 'Sym::1', 'y']]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.flatcode" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[['set', 'c', 1],\n", " ['add', 'LocalSym::0', 0, 2],\n", " ['add', 'Localy', 'LocalSym::0', 1],\n", " ['mul', 'LocalSym::1', 'Localy', 'Localy'],\n", " ['mul', 'x::0', 'LocalSym::1', 'Localy'],\n", " ['set', 'c::1', 2],\n", " ['add', 'LocalSym::0', 0, 2],\n", " ['add', 'Localy', 'LocalSym::0', 1],\n", " ['mul', 'LocalSym::1', 'Localy', 'Localy'],\n", " ['mul', 'x::2', 'LocalSym::1', 'Localy'],\n", " ['set', 'c::3', 3],\n", " ['add', 'LocalSym::0', 0, 2],\n", " ['add', 'Localy', 'LocalSym::0', 1],\n", " ['mul', 'LocalSym::1', 'Localy', 'Localy'],\n", " ['mul', 'x::4', 'LocalSym::1', 'Localy'],\n", " ['set', 'c::5', 4],\n", " ['add', 'LocalSym::0', 0, 2],\n", " ['add', 'Localy', 'LocalSym::0', 1],\n", " ['mul', 'LocalSym::1', 'Localy', 'Localy'],\n", " ['mul', 'x::6', 'LocalSym::1', 'Localy'],\n", " ['set', 'c::7', 5],\n", " ['add', 'LocalSym::0', 0, 2],\n", " ['add', 'Localy', 'LocalSym::0', 1],\n", " ['mul', 'LocalSym::1', 'Localy', 'Localy'],\n", " ['mul', 'x::8', 'LocalSym::1', 'Localy'],\n", " ['add', '~out', 'x::8', 'k']]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mimc.flatcode" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The format of a flatcode line is:\n", "\n", "$$\n", "\\left[Op, Out, S_a, S_b\\right]\n", "$$" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['~one',\n", " 'x',\n", " 'k',\n", " '~out',\n", " 'c',\n", " 'LocalSym::0',\n", " 'Localy',\n", " 'LocalSym::1',\n", " 'x::0',\n", " 'c::1',\n", " 'LocalSym::0',\n", " 'Localy',\n", " 'LocalSym::1',\n", " 'x::2',\n", " 'c::3',\n", " 'LocalSym::0',\n", " 'Localy',\n", " 'LocalSym::1',\n", " 'x::4',\n", " 'c::5',\n", " 'LocalSym::0',\n", " 'Localy',\n", " 'LocalSym::1',\n", " 'x::6',\n", " 'c::7',\n", " 'LocalSym::0',\n", " 'Localy',\n", " 'LocalSym::1',\n", " 'x::8']" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mimc.var" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The format of variable is\n", "\n", "$$\n", "[One, Input_0, \\cdots, Input_n, Output, S_0, S_1, \\cdots, S_n]\n", "$$\n" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [], "source": [ "assert len(mimc.A[0]) == len(mimc.var)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For each line of flatcodes, we have $A_i.s \\circ B_i.s == C_i.s$" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[BN128FP::0x1,\n", " BN128FP::0x2a,\n", " BN128FP::0x0,\n", " BN128FP::0x1b,\n", " BN128FP::0x1,\n", " BN128FP::0x2,\n", " BN128FP::0x3,\n", " BN128FP::0x9,\n", " BN128FP::0x1b,\n", " BN128FP::0x2,\n", " BN128FP::0x2,\n", " BN128FP::0x3,\n", " BN128FP::0x9,\n", " BN128FP::0x1b,\n", " BN128FP::0x3,\n", " BN128FP::0x2,\n", " BN128FP::0x3,\n", " BN128FP::0x9,\n", " BN128FP::0x1b,\n", " BN128FP::0x4,\n", " BN128FP::0x2,\n", " BN128FP::0x3,\n", " BN128FP::0x9,\n", " BN128FP::0x1b,\n", " BN128FP::0x5,\n", " BN128FP::0x2,\n", " BN128FP::0x3,\n", " BN128FP::0x9,\n", " BN128FP::0x1b]" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s = mimc.witness(F(42))\n", "s" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sum(mul(mimc.A[0], s)) * sum(mul(mimc.B[0], s)) == sum(mul(mimc.C[0], s))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Gen QAP\n" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "A, B, C = mimc.r1cs" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "qap = QAP(A, B, C)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[BN128FP::0x1,\n", " BN128FP::0x2a,\n", " BN128FP::0x0,\n", " BN128FP::0x1b,\n", " BN128FP::0x1,\n", " BN128FP::0x2,\n", " BN128FP::0x3,\n", " BN128FP::0x9,\n", " BN128FP::0x1b,\n", " BN128FP::0x2,\n", " BN128FP::0x2,\n", " BN128FP::0x3,\n", " BN128FP::0x9,\n", " BN128FP::0x1b,\n", " BN128FP::0x3,\n", " BN128FP::0x2,\n", " BN128FP::0x3,\n", " BN128FP::0x9,\n", " BN128FP::0x1b,\n", " BN128FP::0x4,\n", " BN128FP::0x2,\n", " BN128FP::0x3,\n", " BN128FP::0x9,\n", " BN128FP::0x1b,\n", " BN128FP::0x5,\n", " BN128FP::0x2,\n", " BN128FP::0x3,\n", " BN128FP::0x9,\n", " BN128FP::0x1b]" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "w = mimc.witness(F(42))\n", "w" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "assert qap.verify(*qap.proof(F(112221), w))" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [], "source": [ "A, B, C, Z, H = qap.proof(F(112221), w)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## PGHR13" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "ename": "ModuleNotFoundError", "evalue": "No module named 'klefki.curves.barreto_naehrig'", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mModuleNotFoundError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32mfrom\u001b[0m \u001b[0mklefki\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurves\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbarreto_naehrig\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mbn128\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 2\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0mklefki\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0malgebra\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mutils\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mrandfield\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0moperator\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0madd\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0mfunctools\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mreduce\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mModuleNotFoundError\u001b[0m: No module named 'klefki.curves.barreto_naehrig'" ] } ], "source": [ "from klefki.curves.barreto_naehrig import bn128\n", "from klefki.algebra.utils import randfield\n", "from operator import add\n", "from functools import reduce\n", "\n", "A, B, C, Z = R1CS2QAP(*r1cs, F(42), field=F)\n", "ECG = bn128.ECGBN128\n", "G1 = bn128.ECGBN128.G1\n", "G2 = bn128.ECGBN128.G2\n", "e = bn128.ECGBN128.e\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class PGHR13:\n", " def __init__(self, F, G):\n", " \"\"\"\n", " Setup toxic: t, k_a, k_b and k_c\n", " \n", " \"\"\"\n", " self.G = G\n", " self.F = F\n", " self.k_a = randfield(F)\n", " self.k_b = randfield(F)\n", " self.k_c = randfield(F)\n", " \n", " @property\n", " def toxic(self):\n", " return (self.t, self.k_a, self.k_b, self.k_c)\n", " \n", " def setup(self, A, B, C, H, Z):\n", " self.pi_a = reduce(add, [self.G@a for a in A])\n", " self.pi_a_ = self.pi_a @ self.k_a\n", " \n", " self.pi_b = reduce(add, [self.G@b for b in B])\n", " self.pi_b_ = self.pi_b @ self.k_b\n", " \n", " self.pi_c = reduce(add, [self.G@c for c in C])\n", " self.pi_c_ = self.pi_c @ self.k_c\n", " \n", " self.pi_h = self.G @ H\n", " self.pi_z = self.G @ Z\n", " \n", " @property\n", " def pi(self):\n", " return (self.pi_a, self.pi_b, self.pi_c)\n", " \n", " def check(self):\n", " return G.e(self.pi_a, self.pi_b) / G.e(self.pi_c, self.G) == G.e(self.pi_h, self.pi_z)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.2" } }, "nbformat": 4, "nbformat_minor": 4 }